package LineCode.Recruit2017.滴滴出行;

import java.util.Scanner;

/**
 * 给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
 * 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。
 */
public class 数字和为sum的方法数 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {

            //输入
            int n = sc.nextInt();
            int sum = sc.nextInt();
            int[] arrs = new int[n];
            for (int i = 0; i < n; i++) {
                arrs[i] = sc.nextInt();
            }

            //处理
            long [] dp = new long[sum+1];
            dp[0] = 1;
            for (int i = 0; i < n; i++) {
                for (int j = sum; j >= arrs[i] ; j--)
                    dp[j] += dp[j-arrs[i]];
            }

            //输出
            System.out.println(dp[sum]);

        }
    }
}
